"""
LeetCode 热题

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

要解决合并重叠区间的问题，我们可以按照以下步骤进行：
排序：首先按照每个区间的起始位置对区间进行排序。
合并区间：遍历排序后的区间，合并重叠的区间。
具体步骤如下：
排序：使用 sorted 函数对区间按起始位置进行排序。
合并：遍历排序后的区间，如果当前区间的起始位置小于等于前一个区间的结束位置，则合并这两个区间；否则，将当前区间加入结果列表。

"""
from collections import deque, Counter


class Solution(object):
    def merge(self, intervals):
        """
        合并所有重叠的区间，并返回一个不重叠的区间数组。

        参数:
        intervals: List[List[int]]，区间集合，其中单个区间为 intervals[i] = [starti, endi]。

        返回:
        List[List[int]]，合并后的不重叠区间数组。
        """
        if not intervals:
            return []

        # 按区间的起始位置排序
        intervals.sort(key=lambda x: x[0])

        # 初始化结果列表和当前区间
        merged = []
        current_interval = intervals[0]

        for interval in intervals[1:]:
            # 如果当前区间的起始位置小于等于前一个区间的结束位置，则合并
            if interval[0] <= current_interval[1]:
                current_interval[1] = max(current_interval[1], interval[1])
            else:
                # 否则，将当前区间加入结果列表，并更新当前区间
                merged.append(current_interval)
                current_interval = interval

        # 添加最后一个区间
        merged.append(current_interval)

        return merged

if __name__ == '__main__':
    a = Solution()
    print(a.merge([[1, 3], [2, 6], [8, 10], [15, 18]]))  # 输出应为 [[1, 6], [8, 10], [15, 18]]
    print(a.merge([[1, 4], [4, 5]]))  # 输出应为 [[1, 5]]
    print(a.merge([[1, 3]]))  # 输出应为 [[1, 3]]
    print(a.merge([[1, 4], [2, 3]]))  # 输出应为 [[1, 4]]
